{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Greatest Common Divisor of Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: gcdOfStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的最大公因子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>对于字符串&nbsp;<code>s</code> 和&nbsp;<code>t</code>，只有在&nbsp;<code>s = t + ... + t</code>（<code>t</code> 自身连接 1 次或多次）时，我们才认定&nbsp;“<code>t</code> 能除尽 <code>s</code>”。</p>\n",
    "\n",
    "<p>给定两个字符串&nbsp;<code>str1</code>&nbsp;和&nbsp;<code>str2</code>&nbsp;。返回 <em>最长字符串&nbsp;<code>x</code>，要求满足&nbsp;<code>x</code> 能除尽 <code>str1</code> 且 <code>x</code> 能除尽 <code>str2</code></em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>str1 = \"ABCABC\", str2 = \"ABC\"\n",
    "<strong>输出：</strong>\"ABC\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>str1 = \"ABABAB\", str2 = \"ABAB\"\n",
    "<strong>输出：</strong>\"AB\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>str1 = \"LEET\", str2 = \"CODE\"\n",
    "<strong>输出：</strong>\"\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= str1.length, str2.length &lt;= 1000</code></li>\n",
    "\t<li><code>str1</code>&nbsp;和&nbsp;<code>str2</code>&nbsp;由大写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [greatest-common-divisor-of-strings](https://leetcode.cn/problems/greatest-common-divisor-of-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [greatest-common-divisor-of-strings](https://leetcode.cn/problems/greatest-common-divisor-of-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ABCABC\"\\n\"ABC\"', '\"ABABAB\"\\n\"ABAB\"', '\"LEET\"\\n\"CODE\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        \n",
    "        if len(str1) < len(str2):\n",
    "            str1,str2 = str2, str1\n",
    "        N1 = len(str1)\n",
    "        N2 = len(str2)\n",
    "        \n",
    "        if str1[:N2]!= str2:\n",
    "            return \"\"\n",
    "\n",
    "        def divide(str1,length):\n",
    "            if len(str1)%length:return False\n",
    "            return str1[:length]*(len(str1)//length) == str1\n",
    "        \n",
    "        ans =0\n",
    "        for i in range(1,N2+1):\n",
    "            if divide(str1,i) and divide(str2,i):\n",
    "                ans = i\n",
    "        return str2[:ans]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        if  str1 + str2 != str2 + str1:\n",
    "            return \"\"\n",
    "        \n",
    "        else:\n",
    "            m = max(len(str1),len(str2))\n",
    "            n = min(len(str1),len(str2))\n",
    "            r = m % n\n",
    "            while r != 0:\n",
    "                m, n = n, r\n",
    "                r = m % n\n",
    "            \n",
    "            return str1[:n]\n",
    "                 \n",
    "                \n",
    "            # difference = len(str1)-len(str2)\n",
    "            # if difference==0:\n",
    "            #     return str1\n",
    "            # elif difference > 0:\n",
    "            #     str1 = str1[len(str2): len(str1)]\n",
    "            # else:\n",
    "            #     str2 = str2[len(str1): len(str2)]\n",
    "                \n",
    "            # return self.gcdOfStrings(str1,str2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        if str1+str2!=str2+str1:\n",
    "            return \"\"\n",
    "        return str1[0:math.gcd(len(str1), len(str2))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        s1 = str1 * 2\n",
    "        s2 = str2 * 2\n",
    "\n",
    "        ans = ''\n",
    "        for i in range(1, min(len(str1), len(str2)) + 1):\n",
    "            if str1[:i] != str2[:i]:\n",
    "                return ''\n",
    "\n",
    "            if len(str1) % i == 0 and len(str2) % i == 0 and s1.find(str1, i) == i and s2.find(str2, i) == i:\n",
    "                ans = s1[:i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        candidate_len = math.gcd(len(str1), len(str2))\n",
    "        candidate = str1[: candidate_len]\n",
    "        if candidate * (len(str1) // candidate_len) == str1 and candidate * (len(str2) // candidate_len) == str2:\n",
    "            return candidate\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        len1,len2 = len(str1),len(str2)\n",
    "        if len1 > len2:\n",
    "            str_max = str1\n",
    "            str_min = str2\n",
    "            max_l = len1\n",
    "            min_l = len2\n",
    "        else:\n",
    "            str_max = str2\n",
    "            str_min = str1\n",
    "            max_l = len2\n",
    "            min_l = len1\n",
    "        if str1[:min_l] != str2[:min_l]:\n",
    "            return \"\"\n",
    "        \n",
    "        for i in range(min_l ):\n",
    "            step = min_l - i\n",
    "            if max_l % step == 0 and min_l % step == 0:\n",
    "                str_temp = str_max[:step]\n",
    "                j = step\n",
    "                while j < max_l:\n",
    "                    if str_max[j:j+step] == str_temp:\n",
    "                        j += step\n",
    "                    else:\n",
    "                        break\n",
    "                if j == max_l:\n",
    "                    return str_temp\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "###### 辗转相除法 ######\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        if len(str1) < len(str2):\n",
    "            str1, str2 = str2, str1\n",
    "        if not str2 or not str1.startswith(str2):\n",
    "            return \"\"\n",
    "        i = 0\n",
    "        while str1[i: i + len(str2)] == str2:\n",
    "            i += len(str2)\n",
    "        if i == len(str1):\n",
    "            return str2\n",
    "        return self.gcdOfStrings(str2, str1[i:])\n",
    "\n",
    "# ###### 枚举 ######\n",
    "# class Solution:\n",
    "#     def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "#         for length in range(min(len(str1), len(str2)), 0, -1):\n",
    "#             if len(str1) % length == 0 and len(str2) % length == 0:\n",
    "#                 if str1[: length] * (len(str1) // length) == str1 and str1[: length] * (len(str2) // length) == str2:\n",
    "#                     return str1[: length]\n",
    "#         return \"\"\n",
    "\n",
    "###### 枚举优化 ######\n",
    "# class Solution:\n",
    "#     def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "#         candidate_len = math.gcd(len(str1), len(str2))\n",
    "#         candidate = str1[: candidate_len]\n",
    "#         if candidate * (len(str1) // candidate_len) == str1 and candidate * (len(str2) // candidate_len) == str2:\n",
    "#             return candidate\n",
    "#         return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        return str1[: math.gcd(len(str1), len(str2))]  if str1 + str2 == str2 + str1 else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        return str1[: math.gcd(len(str1), len(str2))]  if str1 + str2 == str2 + str1 else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        def valid(s1,s2):\n",
    "            if len(s1) % len(s2):\n",
    "                return False\n",
    "            return s2 * (len(s1) // len(s2)) == s1\n",
    "\n",
    "        s = []\n",
    "        for i in range(min(len(str1),len(str2))):\n",
    "            if str1[i] == str2[i]:\n",
    "                s.append(str1[i])\n",
    "            else:\n",
    "                break\n",
    "        for i in range(len(s) - 1,-1,-1):\n",
    "            t = ''.join(i for i in s[:i + 1])\n",
    "            if valid(str1,t) and valid(str2,t):\n",
    "                return t\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        l1 = len(str1)\n",
    "        l2 = len(str2)\n",
    "        # 默认第一个字符串数最长的\n",
    "        if l1 == l2:\n",
    "            if str1 == str2:\n",
    "                return str1\n",
    "            else:\n",
    "                return ''\n",
    "\n",
    "        # if l1 < l2:\n",
    "        #     str1, str2 = str2, str1\n",
    "        #     l1, l2 = l2, l1\n",
    "\n",
    "        for i in range(1, l2//2 + 2):\n",
    "            t = str2[:l2//i]\n",
    "            p = re.compile(f'({t})*')\n",
    "            if p.fullmatch(str2) and p.fullmatch(str1):\n",
    "                return t\n",
    "\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        factor1 = get_factors(str1)\n",
    "        factor2 = get_factors(str2)\n",
    "        factors = factor1 & factor2\n",
    "        max_factor = \"\"\n",
    "        max_length = 0\n",
    "        for fac in factors:\n",
    "            if len(fac) > max_length:\n",
    "                max_length = len(fac)\n",
    "                max_factor = fac\n",
    "        return max_factor\n",
    "\n",
    "def get_factors(str_A):\n",
    "    if len(str_A) == 0:\n",
    "        return str_A\n",
    "    num = 0\n",
    "    length = len(str_A)\n",
    "    factors = set()\n",
    "    while num <= length:\n",
    "        if devide(str_A, str_A[:num]):\n",
    "            factors.add(str_A[:num])\n",
    "        num += 1\n",
    "    return factors\n",
    "        \n",
    "def devide(str_A, str_B):\n",
    "    l_b = len(str_B)\n",
    "    l_a = len(str_A)\n",
    "    if l_a == 0 or l_b == 0:\n",
    "        return True\n",
    "    elif l_b > l_a:\n",
    "        return False\n",
    "    else:\n",
    "        if str_A[:l_b] == str_B:\n",
    "            return devide(str_A[l_b:], str_B)\n",
    "        else:\n",
    "            return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        n, m = len(str1), len(str2)\n",
    "        res = 0\n",
    "        for i in range(1, min(n, m)+1):\n",
    "            if n % i == 0 and m % i == 0 and str1 == str1[:i] * (n//i) and str2 == str1[:i] * (m//i):\n",
    "                res = i\n",
    "        \n",
    "        return str1[:res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        for i in range(min(len(str1),len(str2)),0,-1):\n",
    "            if len(str1)%i == 0 and len(str2)%i == 0:\n",
    "                if str1.count(str1[:i])*len(str1[:i]) == len(str1) and str2.count(str1[:i])*len(str1[:i]) == len(str2):\n",
    "                    return str1[:i]\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        candidate_len = math.gcd(len(str1), len(str2))\n",
    "        candidate = str1[: candidate_len]\n",
    "        if str1 + str2 == str2 + str1:\n",
    "            return candidate\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        candidate_len = math.gcd(len(str1),len(str2))\n",
    "        candidate = str1[:candidate_len]\n",
    "        if str1==candidate*(len(str1)//candidate_len) and str2==candidate*(len(str2)//candidate_len):\n",
    "            return candidate\n",
    "        return \"\"\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        if len(str1)<len(str2):\n",
    "           return self.cal_x(str1,str2)\n",
    "        else:\n",
    "            return self.cal_x(str2,str1)\n",
    "\n",
    "    def cheng(self,x,y):\n",
    "        outs=\"\"\n",
    "        for i in range(y):\n",
    "            outs+=x\n",
    "        return outs\n",
    "\n",
    "    def cal_x(self,str1,str2):\n",
    "        final_outs=\"\"\n",
    "        pre=\"\"\n",
    "        max_len=0\n",
    "        for i in range(len(str1)):\n",
    "            outs=pre+str1[i]\n",
    "            yu=len(str2)//len(outs)\n",
    "            if outs not in str2:\n",
    "                pre=''\n",
    "                continue\n",
    "            else:\n",
    "                pre=outs\n",
    "                yu2=len(str1)//len(outs)\n",
    "                if len(outs)>max_len and str1==self.cheng(outs,yu2) and str2==self.cheng(outs,yu):\n",
    "                    final_outs=outs\n",
    "        return final_outs\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        if len(str1) > len(str2):\n",
    "            str1, str2 = str2, str1\n",
    "        maxStr = \"\"\n",
    "        isFind = True\n",
    "        for i in range(len(str1)):\n",
    "            cur = str1[:i+1]\n",
    "            print(cur)\n",
    "            if cur * (len(str2)//(i+1)) == str2 and cur * (len(str1)//(i+1)) == str1:\n",
    "                maxStr = cur\n",
    "        return maxStr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(self, int1, int2):\n",
    "        if int1 < int2:\n",
    "            temp = int1\n",
    "            int1 = int2\n",
    "            int2 = temp\n",
    "        if int1%int2 == 0:\n",
    "            return int2\n",
    "        else:\n",
    "            return self.gcd(int2, int1%int2)\n",
    "\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        if str1+str2 == str2+str1:\n",
    "            return str1[:self.gcd(len(str1), len(str2))]    \n",
    "        else:\n",
    "            return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        candidate_len = math.gcd(len(str1), len(str2))\n",
    "        print(candidate_len)\n",
    "        candidate = str1[: candidate_len]\n",
    "        if str1 + str2 == str2 + str1:\n",
    "            return candidate\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdOfStrings(self, str1: str, str2: str) -> str:\n",
    "        # 就是找字符串的最大公约子串，但不是求两个字符串长度的最大公约数，还要加额外的判断条件\n",
    "        n1 = len(str1)\n",
    "        n2 = len(str2)\n",
    "        if n1 == n2 and str1 != str2: # 下面的代码无法处理这种情况，这里补充处理\n",
    "            return ''\n",
    "        min_num = min(n1, n2)\n",
    "        for i in range(min_num, 0, -1): # 因为要最长公约子串，所以倒叙遍历\n",
    "            if n1 % i == 0 and n2 % i == 0 and str1[:i]*(n1//i) == str1 and str2[:i]*(n2//i) == str2 and str1[:i] == str2[:i]:\n",
    "                return str1[:i]\n",
    "        return ''\n",
    "            \n",
    "        \n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
